package com.banyuan.lesson.散列表;

/*
* 散列表的java实现
* 目的：根据一个关键字查询到对应的对象
* 通过hashcode实现
* hashcode 整数值
* hashcode冲突
* key.hashcode() & (arr.length -1)好处：
* 1、位运算速度快；
* 2、不会改变数值；
* 3、会截取与length相等的hashcode值；
*
* java的hashmap实现原理，数组+链表+红黑树；
* 当某个桶里的元素大于等于8的时候，链表会升级成红黑树；
* 当个数减为6个的时候，红黑树又转为链表；
* 默认的桶的个数是16，默认的负载因子是0.75；
* 当size大于桶的个数*负载因子，会reszie，扩容（桶的个数会double，还要元素的迁移）；
* 对于每个桶的链表，元素的插入，当下的11版本，用的是尾插法，避免并发情况下，因为可能生成链表的闭环，导致死锁；
*
* 实现hashcode和equals;
* */
public class HashMapDemo {

    private Entry[] arr = new Entry[4];
    private int size;

    public void put(Object key, Object value) {
        int index = key.hashCode() & (arr.length - 1);
        if (arr[index] == null){
            arr[index] = new Entry(key,value);
            size++;
            return;
        }
        Entry temp = arr[index];
        while(temp.getNext() != null){
            temp = temp.getNext();
        }
    }

    public Object get(Object key) {
        if (size == 0) {
            throw new NullPointerException();
        }
        Object temp = null;
        for (int i = 0; i < size; i++) {
            if (arr[i].getKey().equals(key)) {
                temp = arr[i].getValue();
            }
        }
        if (temp == null) {
            return -1;
        } else {
            return temp;
        }
    }

    public static void main(String[] args) {
        HashMapDemo map = new HashMapDemo();
        map.put("aaa", 111);
        map.put("bbb", 222);
        map.put("ccc", 333);
        map.put("ddd", 444);
        System.out.println(map.get("ccc"));
    }

}

class Entry {
    private Object key;
    private Object value;
    private Entry next;


    public Entry() {
    }

    public Entry(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

    public Object getKey() {
        return key;
    }

    public void setKey(Object key) {
        this.key = key;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public Entry getNext() {
        return next;
    }

    public void setNext(Entry next) {
        this.next = next;
    }
}
